import collections

#===============================================================================
#                                SUBSTITUTIONS
#===============================================================================
class RequireStringError(ValueError):
    pass

def filter_fmt(fmt):
    return list(s.strip() for s in fmt.split('|'))

def filter_fmt_math(fmt):
    '''
    Return the substitution rule in a form of a list of filters given the content '
    fmt' inside the substitution string. 
    
    The fmt string is of the form: 
    
        name [| filter1 [| filter2 | ... ]]
    
    It can also have a explicit sign and parenthesis, such as in
        
        fmt = '+(name | filter1)'
        fmt = '-name'
        fmt = '(name | filter1 | filter2)'
        
    '''
    # check for explicit signs (last filter to apply)
    fmt = fmt.strip()
    if fmt.startswith(('+', '-')):
        sign, fmt = fmt[0], fmt[1:]
        sign_filter = { '+': 'plussign', '-': 'minussign' }[sign]
        fmt = fmt.strip()
        filters = [ sign_filter ]
    else:
        filters = []

    # check for parens
    if fmt.startswith('('):
        fmt = fmt[1:-1]
        fmt = fmt.strip()
        filters.insert(0, 'forceparens')

    # find all explicit filters
    fmt = fmt.split('|')
    return [ s.replace('-', '_') for s in fmt + filters ]

def get_subs(json, brakets=('{', '}'), escape=('{{', '}}'), base='$', filter_fmt=filter_fmt):
    '''Locate all strings with substitutions of the type "{ variable|filter }" 
    and build the corresponding rules based on the applied filters and the 
    location of the substitution in the JSON structure.  
    
    Arguments
    ---------
    
    json : lists and dicts
        Any JSON-like structure
    brakets : 2-tuple of strings
        Opening and closing and symbols that surrounds the substitution rules
    escape : 2-tuple of strings
        Escape symbols used to avoid opening a substitution rule
    

    Example
    -------
    
    >>> json = { 'root': { 'foo': 'bar', 'ham': 'My breakfast is { food|witheggs }' }}
    >>> get_subs(json)
    {'$.root.ham': ['My breakfast is {0}', [['food', 'witheggs']]]}
    '''

    all_subs = {}
    lbrace, rbrace = brakets
    lesc, resc = escape
    if not (lbrace in lesc and rbrace in resc):
        raise ValueError('invalid escape string!')
    for (p, v) in walk(json, base=base):
        if not v or not isinstance(v, basestring):
            continue
        my_subs = process_string(v, lbrace, rbrace, lesc, resc, filter_fmt)
        if my_subs is not None:
            all_subs[p] = my_subs
    return all_subs

def process_string(st, lbrace, rbrace, lesc, resc, filter_fmt):
    # Process format string
    res = process_string_worker(st, lbrace, rbrace, lesc, resc, filter_fmt)
    if res is None:
        return None
    else:
        fmt_string, vars = res

    # Fix curly braces to work with Python's str.format() method    
    fmt_string = [ s.replace('{', '{{').replace('}', '}}') for s in fmt_string ]

    # Alternate between string data string and positional substitutions
    alternate = []
    vars_size = len(vars)
    for i, d in enumerate(fmt_string):
        alternate.append(d)
        if i < vars_size:
            alternate.append('{%s}' % i)
    fmt_string = ''.join(alternate)

    return [fmt_string, vars]

def process_string_worker(st, lbrace, rbrace, lesc, resc, filter_fmt, pre=None, vars=None):
    if pre is None:
        pre = []
    else:
        pre = list(pre)
    if vars is None:
        vars = []

    # Partition string in the hope that it is not a escape sequence.
    prefix, _, pos = st.partition(lbrace)

    if not pos and not vars:
        return None
    elif not pos:
        pre.append(prefix.replace(resc, rbrace))
        result = (pre, vars)
    else:
        # Check if it is not an escape sequence, rather than an opening brace.
        maybe_esc = st[:len(prefix) + len(lesc)]
        if lesc in maybe_esc:
            prefix, _, pos = st.partition(lesc)
            prefix = prefix.replace(resc, rbrace) + lbrace
            fmt_string, vars = process_string_worker(pos, lbrace, rbrace, lesc, resc, filter_fmt, vars=vars)

            # Join format string
            if pre:
                pre[-1] = pre[-1] + prefix
                if fmt_string:
                    pre[-1] = pre[-1] + fmt_string.pop(0)
            elif fmt_string:
                fmt_string[0] = prefix + fmt_string[0]
            else:
                return None
            pre.extend(fmt_string)
            result = (pre, vars)
        else:
            # Continue knowing that string was not partitioned in a escape sequence.
            pre.append(prefix.replace(resc, rbrace))
            fmt, _, pos = pos.partition(rbrace)
            vars.append(filter_fmt(fmt))
            result = process_string_worker(pos, lbrace, rbrace, lesc, resc, filter_fmt, pre=pre, vars=vars)
    return result

def compute_subs(substitutions, variables={}, filters={}, empty=None):
    '''
    Compute all substitutions from the given variables and filters and
    return a dictionary mapping paths to the computed substitution strings.
    
    Variables
    ---------
    
    substitution: Mapping from jpaths to substitutions.
        Structure that define substitutions. It is the output of the get_subs()
        function.
        
    variables: Mapping
        Maps variables names to their values. 
    
    filters: Mapping
        Maps filter names to their values. If filter['DEFAULT'] is set, it 
        will be used whenever a RequireStringError is raised. The default filter
        is also applied at the end of the filters list. The default behavior is 
        to convert the object to unicode.
        
    empty: str
        If this variable is set, it silently fill in any entry with a missing 
        variable or filter. Otherwise, an exception is raised.
        
    Example
    -------
    >>> json = { 'hello': 'Hello {x}!'}
    >>> subs = get_subs(json)
    >>> compute_subs(subs, {'x': 'World'})
    {'$.hello': 'Hello World!'}
    '''
    default_f = filters.get('DEFAULT', unicode)
    SubsType_result = {}
    for path, (text, vars) in substitutions.items():
        fmt_vars = []
        for varlst in vars:
            varname = varlst[0]
            filters = varlst[1:]
            try:
                var = variables[varname]
                filter_f = [ filters[f] for f in varlst[1:] ]
            except KeyError, ex:
                if empty is None:
                    if not varname in variables:
                        raise KeyError('variable not found, ' + varname)
                    else:
                        for fname in varlst[1:]:
                            if not fname in filters:
                                raise KeyError('filter not found, ' + fname)
                else:
                    fmt_vars.append(empty)
                    continue

            # apply filters
            for f in filter_f:
                try:
                    var = f(var)
                except RequireStringError:
                    var = f(default_f(var))
            fmt_vars.append(default_f(var))

        text = text.format(*fmt_vars)
        SubsType_result[path] = text

    return SubsType_result

if __name__ == '__main__':
    #json = { 'root': { 'foo': 'bar', 'ham': 'My breakfast is { food | witheggs }'}, 'strings': ['Foo', 'Foo {bar}', '{foo} Bar', '{teste}', '{x1}{x2} {x3}', 'multi {{{x1}}}']}
    json = { 'st': 'multi ||x1|| asd'}
    subs = get_subs(json, brakets=('||', '||'), escape=('\||', '\||'))
    print 'subs', subs
    print compute_subs(subs, {'x1': 1})

    import doctest
    doctest.testmod(optionflags=doctest.REPORT_ONLY_FIRST_FAILURE)
